package site.wanjiahao;

/**
 * 最长公共子序列
 */
public class LCS {


    public static void main(String[] args) {
        int[] num1 = {1, 3, 5, 9, 10, 30};
        int[] num2 = {1, 4, 9, 10};

        System.out.println(lcs(num1, num2));
    }

    // 动态规划
    static int lcs(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) return 0;
        int[] rowEle = nums1, colEle = nums2;
        // 选取较大的作为行元素，这样列元素相对而言就比较少
        if (nums1.length < nums2.length) {
            rowEle = nums2;
            colEle = nums1;
        }
        // 实际情况下，只用到了left，top，leftTop三个元素，所以可以使用一个列数组来优化
        int[] dp = new int[colEle.length + 1];
        for (int row = 1; row <= rowEle.length; row++) {
            // 记录左上角值，否则会被覆盖
            int cur = 0;
            for (int col = 1; col <= colEle.length; col++) {
                int leftTop = cur;
                cur = dp[col];
                // 如果第i项序列相同
                if (rowEle[row - 1] == colEle[col - 1]) {
                    dp[col] = leftTop + 1;
                } else {
                    dp[col] = Math.max(dp[col], dp[col - 1]);
                }
            }
        }
        return dp[colEle.length];
    }

    // 动态规划
    static int lcs3(int[] nums1, int[] nums2) {
        // 由于上个数据只用到了前面一行，或者当前行，所以dp数组可以优化为行为2的数值
        if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) return 0;
        int[] rowEle = nums1, colEle = nums2;
        // 选取较大的作为行元素，这样列元素相对而言就比较少
        if (nums1.length < nums2.length) {
            rowEle = nums2;
            colEle = nums1;
        }
        int[][] dp = new int[2][colEle.length + 1];
        for (int row = 1; row <= rowEle.length; row++) {
            for (int col = 1; col <= colEle.length; col++) {
                int newRow = row & 1;
                int prevRow =  row - 1 & 1;
                int prevCol = col - 1;
                // 如果第i项序列相同
                if (rowEle[row - 1] == colEle[col - 1]) {
                    dp[newRow][col] = dp[prevRow][prevCol] + 1;
                } else {
                    dp[newRow][col] = Math.max(dp[prevRow][col], dp[newRow][prevCol]);
                }
            }
        }
        return dp[rowEle.length & 1][colEle.length];
    }

    // 动态规划
    static int lcs1(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) return 0;
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        for (int i = 1; i <= nums1.length; i++) {
            for (int j = 1; j <= nums2.length; j++) {
                // 如果第i项序列相同
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[nums1.length][nums2.length];
    }

    // 递归实现
    static int lcs2(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) return 0;
        return lcs1(nums1, nums1.length - 1, nums2, nums2.length - 1);
    }

    static int lcs1(int[] num1, int index1, int[] num2, int index2) {
        if (index1 < 0 || index2 < 0) return 0;
        if (num1[index1] != num2[index2]) {
            return Math.max(lcs1(num1, index1 - 1, num2, index2),
                    lcs1(num1, index1, num2, index2 - 1));
        }
        return lcs1(num1, index1 - 1, num2, index2 - 1) + 1;
    }
}
